package Tree;
import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {

    //定义树的结点类
    static class TreeNode {
        public char val;
        //定义两个变量存左右结点的地址
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;//因为左右节点的地址是未知的所以我们不给构造方法传这两个的值
        }
    }

    //以穷举的方式 创建一颗二叉树
    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
       TreeNode H = new TreeNode('H');

        //创建根结点
        A.left = B;
        A.right = C;

        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;

       E.right = H;

        //将根结点返回,以便查询
        return A;
    }

    //通过递归实现前中后序遍历
    //前序遍历-根左右
    public void  preOrder(TreeNode root){
        //如果根节点为空了,说明就不需要再遍历了,直接返回即可
        //**每次遍历的时候每一个节点都有机会成为根节点
        if(root == null){
            return;//空节点不需要遍历
        }
        System.out.print(root.val+ " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历 - 左根右
    public void midOrder(TreeNode root){
        if(root == null){
            return;
        }
        midOrder(root.left);
        System.out.print(root.val+" ");
        midOrder(root.right);
    }

    //后序遍历 - 左右根
    public void behOrder(TreeNode root){
        if(root == null){
            return;
        }
        behOrder(root.left);
        behOrder(root.right);
        System.out.print(root.val+" ");
    }

    //****找树的总节点数
    //方法1:根据遍历特点,每个节点都可能是root,
    //所以当我的root不为空时,每次定义一个变量去计算root的数量即可
    int NodeNum = 0;
    public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        NodeNum ++;
        size(root.left);
        size(root.right);
        return NodeNum;
    }

    //方法2:将每一个节点看作是一颗树,即这个树的节点个数= 左节点的结点数+右节点的节点数+root
    public int size2(TreeNode root){
        if (root == null) {
            return 0;
        }
        int NodeNum = size2(root.left) + size2(root.right) + 1;//根不为null根结点就只有1个~
        return NodeNum;
    }


    //****找叶子结点个数
    //方法①:只要他是根节点不为空,并且左右节点为空,说明他就是叶子结点
    //定义一个临时变量去记录叶子结点的数量
    int leaf = 0;
    public int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            leaf++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return leaf;
    }

    //方法②:根据树的特点,叶子结点就是根节点的左叶子节点,加根的右叶子结点
    //通过递归的方式,把每个节点都看成根节点,然后叶子结点数 = 左叶子 + 右叶子
    public int getLeafNodeCount2(TreeNode root) {
        if(root == null){
            return 0 ;
        }
        //如果左子叶和右子叶为空,此时叶子结点就是根节点自己,返回1
        if(root.left == null && root.right == null){
            return 1;
        }
        int leaf = getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
        return leaf;
    }

    //****找第K层的节点数
    public int KNode(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        //第K层的节点数就是,从根节点一直往下走,直到K=1时,这层的节点数之和,
        //eg:K=2,找第二层的节点数,就是根节点的左子树的节点数+根节点的右子树的节点数之和
        int knode = KNode(root.left, k - 1) + KNode(root.right, k - 1);
        return knode;
    }

    //****获取二叉树的高度
    //整棵树的高度的最大值 = 左子树高度 和 右子树高度 中 最大的那个 +1
    //写法1:
    public int TreeHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        int H = Math.max(TreeHeight(root.left),TreeHeight(root.right))+1;
        return H;
    }

    //写法2:三目运算符,谁大取谁 --> 会超出时间限制
    public int TreeHeight2(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        int leftHeight = TreeHeight2(root.left);
        int rightHeight = TreeHeight2(root.right);
        return (leftHeight > rightHeight ? leftHeight : rightHeight)+ 1;
    }

    //****检测值为value的元素是否存在
    public TreeNode find(TreeNode root , int val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        //递归左子树,从左子树查找元素
        TreeNode left = find(root.left , val);
        if (left != null){//左子树查找不为空,说明找到了,返回左子树的值
            return left;
        }
        //递归右子树从右子树查找元素
        TreeNode right = find(root.right , val);
        if(right != null){//右子树查找不为空,说明找到了,返回右子树的值
            return right;
        }
        return null;
    }

    //****判断两颗树是否相等
    //1.根节点
    //时间复杂度:O(min(M,N));
        public boolean isSameTree(TreeNode p, TreeNode q) {

            //结构先判断是否一样
            //1.结构不一样 -> 左树为空,右树不为空;右树为空,左树不为空
            if(p == null && q != null || p != null && q == null ){
                return false;
            }

            //上面结构情况判断完,下面,说明树都是在结构一样的基础上进行讨论的
            //说明这棵树的根节点要么都为空,要么都不为空
            //2.根结点都为空的情况
            if(p == null && q == null){
                return true;
            }

            //3.根节点不为空,判断左右子树的值是否相等
            if(p.val != q.val){
                return false;
            }

            //代码走到这里说明:p!=null && q != null && 根节点一样
            //递归每棵树的左右节点,将他们当作根节点判断是否相等
            return ( isSameTree(p.left , q.left) && isSameTree(p.right , q.right) );
        }

    //****判断树是否是平衡二叉树
    //方法①:时间复杂度O(n²)
    public boolean isBalanced(TreeNode root) {
        //1.节点为空的情况 -> 是平衡树
        if(root == null){
            return true;
        }

        //2.节点不为空的情况 -> 看高度差
        //判断一颗树是否是平衡二叉树,主要看左右树的高度差是否是<=1;
        //1.计算数的高度
        int left1 = HeightTree(root.left);//根节点的左子树高度
        int right1 = HeightTree(root.right);//根节点的右子树高度

        //***除了判断高度差是否<=1,还需要再判断一下左右子树是否平衡
        if((Math.abs(left1 - right1) <= 1) && isBalanced(root.left) && isBalanced(root.right)){
            return true;
        }

        return false;

    }

    //****定义一个方法用于计算树的高度
    //一棵树的高度等于左右子树最大的那个高度+1
    public int HeightTree(TreeNode root){
        //根节点为空,树的高度为0
        if (root == null){
            return 0;
        }

        //根节点不为空,左子树为空并且右子树为空,树的高度等于1
        if(root.left == null && root.right == null){
            return 1;
        }

        //下面就是根节点不为空,并且左右子树都不会为空的情况
        //通过递归去遍历每一个节点,计算左右子树的高度
        int left = HeightTree(root.left);//左子树高度
        int right = HeightTree(root.right);//右子树高度
        //取得左右子树高度最大的那个高度,加1就是这棵树的高度
        int H = Math.max(left,right) + 1;

        return H;
    }

    //方法②:优化时间复杂度为O(n)
    //在计算高度时就去判断是否是平衡二叉树,就不需要在遍历完树计算完高度以后又遍历一次树去判断它的左右子树是否平衡
    //时间复杂度:O(n)
    public boolean isBalanced2(TreeNode root) {
        //1.节点为空的情况 -> 是平衡树
        if(root == null){
            return true;
        }
        //通过对获取树高度这个方法添加判断平衡二叉树的条件进行优化,在我们
        //判断平衡时只需要调用获取树高度这个方法即可
        //如果将根节点带入这个方法返回的高度值>=0说明这棵树是平衡的,<0则不平衡
        return HeightTree2(root) >= 0;

    }

    //定义一个方法用于计算树的高度
    //一棵树的高度等于左右子树最大的那个高度+1
    public int HeightTree2(TreeNode root){
        //根节点为空,树的高度为0
        if (root == null){
            return 0;
        }

        //下面就是根节点不为空,并且左右子树都不会为空的情况
        //通过递归去遍历每一个节点,计算左右子树的高度
        int left = HeightTree2(root.left);//左子树高度
        int right = HeightTree2(root.right);//右子树高度

//======================================================
        //效率优化:计算完左右子树高度,可以先判断它是不是平衡树
        //是:返回树的高度
        //不是:返回-1
        if(left >= 0 && right >= 0 && Math.abs(left - right) <= 1 ){
            //这里还要增加左右子树高度的条件约束,原因:
            //1.如果我们计算完一颗子树的左右高度left是0,right是-1
            //此时,我们将left - right = 1,他满足平衡树的条件
            //但是我们的右子树高度返回的是-1,它明显是不平衡的
            //所以要给左右子树高度限制范围,它的高度要大于等于0
            return Math.max(left,right)+1;//返回的是平衡树的高度
        }else{
            return -1;
        }
//=======================================================
    }

    //****对称二叉树
    public boolean isSymmetric(TreeNode root) {//判断树是否对称
        if(root == null){
            return true;
        }

        //根结点不为空,调用下面的方法去判断左右子树是否对称
        return isSymmetricChild(root.left,root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        //**(1)结构判断 ->左右子树结构是否相等
        if(leftTree == null && rightTree != null ||
                leftTree != null && rightTree == null){
            return false;//结构不相等的情况
        }

        //(2)结构相等,下面判断值
        //1.左右子树都为空,是平衡树
        if(leftTree == null && rightTree == null){
            return true;
        }

        //2.左右子树不为空,判断:
        //①判断左右子树的值是否相等
        if(leftTree.val != rightTree.val){
            return false;
        }
        //②左右子树的左右分支是否相等
        return isSymmetricChild(leftTree.left,rightTree.right) &&
                isSymmetricChild(leftTree.right,rightTree.left);
        //每次都会遍历到叶子结点,当我遍历到叶子节点时,
        //左右子树都为null,此时会执行1部分的代码,就会返回true.
    }

    //二叉树的程序遍历 -> 返回值为void
    //- 用队列实现
    //- 先把根节点出队,然后如果左右节点不为空将其左右节点入队
    public void levelOrder1(TreeNode root){
        if(root == null){
            return;
        }
        //通过链表实现创建一个存放TreeNode类型元素的队列
        Queue<TreeNode> myqueue = new LinkedList<>();
        //将元素放入创建的队列中
        myqueue.offer(root);
        //判断队列是否为空,空则不用弹出元素,不为空则要出队
        while(!myqueue.isEmpty()){
            //将元素弹出队列
            TreeNode cur = myqueue.poll();
            //打印当前出队元素的值
            System.out.print(cur.val+" ");
            //判断当前节点的左节点是否为空,不为空则将节点元素入队
            if(cur.left != null){
                myqueue.offer(cur.left);
            }
            //判断根节点的右节点是否为空,不为空则将元素入队
            if(cur.right != null){
                myqueue.offer(cur.right);
            }
        }
    }

    //===================================================

    //leetcode的那道题是要将每一层的数据都放到一个数组里面,然后将它们保存在一个二维数组里面

    //关键是:如何确定哪些数据是属于同一层的
    //  我们可以通过**当前队列的节点个数来看现在的节点是在第几层的树**
    //  只要队列里面的元素个数不是0,说明队列当前层的元素还没有出完,每出一个元素,就将它存储到数组里面
    //  直到队列节点数size为0,就将这一层的元素装到二维数组里面

    //外层,循环判断队列是否为空,当队列为空时,说明树的每一层元素都弹出来了,直接返回最后存储所有层元素的二维数组

    public List<List<Character>> levelOrder2(TreeNode root) {
        List<List<Character>> myList = new ArrayList<>();
        if(root == null){
            return myList;//节点为空说明没有元素,返回空数组
        }

        //节点不为空,先创建一个队列用于存放根结点
        Queue<TreeNode> myqueue = new LinkedList<>();
        myqueue.offer(root);
        // 只要队列不为空,就将元素存储到数组里面
        while(!myqueue.isEmpty()){
            //记录当前队列的大小
            int size = myqueue.size();
            // 定义一个一维数组存储每一层的元素
            List<Character> res = new ArrayList<>();
            // 通过while循环遍历每一层的元素,只要队列大小不为0,说明还在同一层
            while(size != 0){
                //弹出队列里面的值
                TreeNode cur = myqueue.poll();
                //将它存储到列表里面
                res.add(cur.val);
                size--;//0
                if(cur.left != null){
                    myqueue.offer(cur.left);
                }
                if(cur.right != null){
                    myqueue.offer(cur.right);
                }
            }
            myList.add(res);//将每一层节点集合的数组放到二维数组里面
        }
        return myList;
    }


    //=======================================
    //判断一颗树是否是完全二叉树

    public boolean isCompleteTree(TreeNode root){
        if(root == null){
            return true;
        }
        //先创建一个队列存储字符数据
        Queue<TreeNode> queue = new LinkedList<>();
        //将根节点的值先入队
        queue.offer(root);
        //队列不为空则弹出元素,带入左右
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();//弹出元素
            if(cur != null){//只要根节点不为空就将其左右节点放到队列里面,左右可为空
                //带入左右
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;//跳出循环
            }
        }

        //上面循环放元素,下面循环遍历队列,判断每一个元素是否为空,null则说明是平衡二叉树
        //有不为null的说明不是平衡二叉树
        while(!queue.isEmpty()){
            TreeNode cur  = queue.poll();
            if (cur != null){
                return false;
            }
        }
        return true;
    }

}
